package cn.fansunion.leecode.array;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import cn.fansunion.leecode.kit.Kit;

/**
 * 两个数组的交集。给定两个数组，编写一个函数来计算它们的交集。 https://leetcode-cn.com/problems/intersection-of-two-arrays/
 * 
 * @author wen.lei@brgroup.com
 *
 *         2021-12-30
 */
public class IntersectionOfTwoArrays {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] nums1 = new int[] {1, 2, 2, 1};
        int[] nums2 = new int[] {2, 2};
        IntersectionOfTwoArrays tota = new IntersectionOfTwoArrays();
        int[] intersectionNums = tota.intersectionList(nums1, nums2);
        Kit.print(intersectionNums);
        int[] intersectionNums3 = tota.intersectionSet(nums1, nums2);
        Kit.print(intersectionNums3);
        int[] intersectionNums4 = tota.intersectionSetGood(nums1, nums2);
        Kit.print(intersectionNums4);
        int[] intersectionNums2 = tota.intersectionHasRepeat(nums1, nums2);
        Kit.print(intersectionNums2);
    }

    /**
     * 2个数组的交集,暴力破解，用List，O(mn)
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersectionList(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j] && !list.contains(nums1[i])) {
                    list.add(nums1[i]);
                }
            }
        }
        // list->array
        int[] nums = new int[list.size()];
        for (Integer index = 0; index < list.size(); index++) {
            nums[index] = list.get(index);
        }
        return nums;
    }

    /**
     * 2个数组的交集,暴力破解，用Set，O(mn)
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersectionSet(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    set.add(nums1[i]);
                }
            }
        }
        // set->array(set没有get(index)方法)
        int[] nums = Kit.setToArray(set);
        return nums;
    }

    /**
     * 2个数组的交集,O(2n)
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersectionSetGood(int[] nums1, int[] nums2) {
        //寻找2个集合，小的用来遍历，多的用来判断是否包含
        int[] numsMin;
        Set<Integer> setMax= new HashSet<>();
        if (nums1.length <= nums2.length) {
            numsMin=nums1;
            for (Integer num : nums2) {
                setMax.add(num);
            }
        } else {
            numsMin=nums2;
            for (Integer num : nums1) {
                setMax.add(num);
            }
        }
        // 交集
        Set<Integer> intersectionSet = new HashSet<>();
        for (int num : numsMin) {
            if (setMax.contains(num)) {
                intersectionSet.add(num);
            }
        }
        int[] nums = Kit.setToArray(intersectionSet);
        return nums;
    }

    /**
     * 临时方法：2个数组的交集，包含了重复的且直接用了nums，可能有多余的0
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersectionHasRepeat(int[] nums1, int[] nums2) {
        int length = nums1.length;
        if (nums2.length < length) {
            length = nums2.length;
        }
        int[] nums = new int[length];
        int size = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                boolean t = nums1[i] == nums2[j];
                if (t) {
                    nums[size] = nums1[i];
                }
            }
        }
        return nums;
    }
}
